Throughout this specification we will be using the term MPEG as a generic reference to a family of international standards set by the Motion Picture Expert Group. MPEG reports to sub-committee 29 (SC29) of the Joint Technical Committee (JTC1) of the International Organization for Standardization (ISO) and the International Electro-technical Commission (IEC).
Throughout this specification the term H.26x will be used as a generic reference to a closely related group of international recommendations by the Video Coding Experts Group (VCEG). VCEG addresses Question 6 (Q.6) of Study Group 16 (SG16) of the International Telecommunications Union Telecommunication Standardization Sector (ITU-T). These standards/recommendations specify exactly how to represent visual and audio information in a compressed digital format. They are used in a wide variety of applications, including DVD (Digital Video Discs), DVB (Digital Video Broadcasting), Digital cinema, and videoconferencing.
Throughout this specification the term MPEG/H.26x will refer to the superset of MPEG and H.26x standards and recommendations.
There are several existing major MPEG/H.26x standards: H.261, MPEG-1, MPEG-2/H.262, MPEG4/H.263. Among these, MPEG-2/H.262 is clearly most commercially significant, being sufficient in many applications for all the major TV standards, including NTSC (National Standards Television Committee) and HDTV (High Definition Television). Of the series of MPEG standards that describe and define the syntax for video broadcasting, the standard of relevance to the present invention is the draft standard ITU-T Recommendation H.264, ISO/IEC 14496-10 AVC, which is incorporated herein by reference and is hereinafter referred to as “MPEG-AVC/H.264”.
A feature of MPEG/H.26x is that these standards are often capable of representing a video signal with data roughly 1/50th the size of the original uncompressed video, while still maintaining good visual quality. Although this compression ratio varies greatly depending on the nature of the detail and motion of the source video, it serves to illustrate that compressing digital images is an area of interest to those who provide digital transmission.
MPEG/H.26x achieves high compression of a video signal through the successive application of five basic mechanisms:    1) Storing the luminance (black & white) detail of the video signal with more horizontal and vertical resolution than the two chrominance (colour) components of the video.    2) Storing only the differences from one area of a video frame to another area of the same frame, thus removing spatially redundant information from a video signal.    3) Storing only the differences from one video frame to another, thus removing temporally redundant information from a video signal.    4) Storing these differences with reduced fidelity, as quantized transform coefficient symbols, to trade-off a reduced number of bits per symbol with increased video distortion.    5) Storing all the symbols representing the compressed video with entropy encoding, to reduce the number of bits per symbol without introducing any additional video signal distortion.
Mechanisms 2) and 3) are accomplished by defining a predicted value for each pixel in a video frame, based on previous and future video frames in a sequence of video frames. The aggregation of these predicted pixel values is referred to as a predicted frame.
The MPEG-AVC/H.264 standard defines a syntax that allows the transmission of prediction parameters that fully describe how to generate the predicted frame from previous and future frames. The MPEG-AVC/H.264 standard also defines the syntax for describing the difference of a video frame from the predicted frame. In general, it is possible to create a predicted frame whereby far fewer bits are required to transmit the prediction parameters and the difference from the predicted frame, than would be required to transmit each pixel value from the original video frame.
Conceptually, the prediction parameters defined in the MPEG-AVC/H.264 standard can be thought of as describing the motion of objects within a sequence of video frames from one frame to the next. The process by which the best prediction parameters are determined is called motion estimation.
This invention addresses an improved method and system to perform motion estimation for MPEG video streams.